/**
 * LCS.java created by zhangzhidong 
 * at 下午10:39:08 2016年9月13日
 */
package algorithm.CIG.string;

/**
 * @author zhangzhidong<br>
 * comment generated at 2016年9月13日下午10:39:08<br>
 * 
 */
public class LCS {
	public static void main(String args[]){
		LCS l = new LCS();
		System.out.println(l.findLCS("zynnqufc",8,"ddbauhkw",8));
	}
	public int findLCS(String A, int n, String B, int m) {
        // write code here
        return get(A.toCharArray(),B.toCharArray());
    }
    int get(char[] a,char[]b){
        //dp[i][j]表示a必须以i结尾，b必须以j结尾的最长公共子序列长度
     	int [][] dp = new int[a.length][b.length];
        if(a[0]==b[0]) dp[0][0]=1;
        for(int i=1;i<a.length;i++){dp[i][0] = (Math.max((a[i]==b[0]?1:0),dp[i-1][0]));}
        for(int j=1;j<b.length;j++){dp[0][j] = (Math.max((a[0]==b[j]?1:0),dp[0][j-1]));}
        for( int i=1;i<a.length;i++){
            for(int j=1;j<b.length;j++){
				if(a[i]==b[i]){
					dp[i][j]=Math.max(Math.max(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1]+1);
                }else{
                    dp[i][j]= Math.max(dp[i][j-1],dp[i-1][j]);
                }
                
            }	
        }
        
        return dp[a.length-1][b.length-1];
        
    }

}
